In some wireless communication networks, procedures are provided that allow a first device to discover other nearby devices that provide a service. For example, various service discovery protocols can be used by low-power devices configured to communicate with other devices in 802.11-based WiFi networks. In some such systems, a first device broadcasts a request for a particular service (e.g., a printing, music, gaming, or other service), and nearby devices that hear the request (and support the requested service) send a response indicating that the device supports the service. To ensure that responses from nearby devices are not missed, and that new devices are accounted for, multiple rounds of discovery requests and responses may be sent by the devices. To reduce the number of these discovery messages, broadcast requests may include identification data indicating those devices that have already been successfully discovered (i.e., successfully identified as supporting the requested service). If a device sees that it has already been discovered, there is no need to transmit additional discovery messages in response to future requests. While this approach can reduce the number of discovery messages that are exchanged, the identification data can be lengthy and generate significant overhead. Using fewer bits to more compactly represent the identification data, however, can lead to ambiguity. In particular, a device may erroneously conclude, based on the abbreviated identification data, that the device has already been discovered.